{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Deep Dark Fraction"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #math #number-theory #simulation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #数学 #数论 #模拟"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: fraction"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #分式化简"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>有一个同学在学习分式。他需要将一个连分数化成最简分数，你能帮助他吗？</p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2019/09/09/fraction_example_1.jpg\" style=\"height: 195px; width: 480px;\" /></p>\n",
    "\n",
    "<p>连分数是形如上图的分式。在本题中，所有系数都是大于等于0的整数。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p>输入的<code>cont</code>代表连分数的系数（<code>cont[0]</code>代表上图的<code>a<sub>0</sub></code>，以此类推）。返回一个长度为2的数组<code>[n, m]</code>，使得连分数的值等于<code>n / m</code>，且<code>n, m</code>最大公约数为1。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>cont = [3, 2, 0, 2]\n",
    "<strong>输出：</strong>[13, 4]\n",
    "<strong>解释：</strong>原连分数等价于3 + (1 / (2 + (1 / (0 + 1 / 2))))。注意[26, 8], [-13, -4]都不是正确答案。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>cont = [0, 0, 3]\n",
    "<strong>输出：</strong>[3, 1]\n",
    "<strong>解释：</strong>如果答案是整数，令分母为1即可。</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>限制：</strong></p>\n",
    "\n",
    "<ol>\n",
    "\t<li><code>cont[i] >= 0</code></li>\n",
    "\t<li><code>1 <= cont的长度 <= 10</code></li>\n",
    "\t<li><code>cont</code>最后一个元素不等于0</li>\n",
    "\t<li>答案的<code>n, m</code>的取值都能被32位int整型存下（即不超过<code>2 ^ 31 - 1</code>）。</li>\n",
    "</ol>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [deep-dark-fraction](https://leetcode.cn/problems/deep-dark-fraction/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [deep-dark-fraction](https://leetcode.cn/problems/deep-dark-fraction/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[3, 2, 0, 2]', '[0, 0, 3]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "from fractions import Fraction\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.can = False\n",
    "\n",
    "    def judgePoint24(self, cards: list) -> bool:\n",
    "        cp = list(cards)\n",
    "        self.dfs(cp)\n",
    "\n",
    "        return self.can\n",
    "\n",
    "    def dfs(self, cards):\n",
    "        if len(cards) == 1:\n",
    "            # print(cards[0])\n",
    "            if abs(cards[0] - 24.0) < 1e-6:\n",
    "                print(cards)\n",
    "                self.can = True\n",
    "            return\n",
    "\n",
    "        for i in range(len(cards)):\n",
    "            for j in range(i + 1, len(cards)):\n",
    "                x, y = Fraction(cards[i]), Fraction(cards[j])\n",
    "                cards.pop(j)\n",
    "                for op in ['+', '-', '*', '/']:\n",
    "                    for seq in [1, 0]:\n",
    "                        if op in ['+', '-', '*']:\n",
    "                            res = eval(str(x) + op + str(y)) if seq else eval(str(y) + op + str(x))\n",
    "                        else:\n",
    "                            if seq:\n",
    "                                if y == 0:\n",
    "                                    continue\n",
    "                                res = Fraction(x, y)\n",
    "                            else:\n",
    "                                if x == 0:\n",
    "                                    continue\n",
    "                                res = Fraction(y,x)\n",
    "\n",
    "                        cards[i] = res\n",
    "                        self.dfs(cards)\n",
    "                cards[i] = x\n",
    "                cards.insert(j, y)\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bestLine(self, points: List[List[int]]) -> List[int]:\n",
    "        INF = float(\"inf\")\n",
    "        N = len(points)\n",
    "        kMap = defaultdict(list)\n",
    "        # points.sort()\n",
    "        from fractions import Fraction \n",
    "\n",
    "        for i in range(N):\n",
    "            x1,y1 = points[i]\n",
    "            for j in range(i+1,N):\n",
    "                x2,y2 = points[j]\n",
    "                k = Fraction(y2-y1,x2-x1) if x2-x1!=0 else INF \n",
    "                if (i,k) not in kMap:\n",
    "                    kMap[(i,k)]=[j,1]\n",
    "                else:\n",
    "                    kMap[(i,k)][0] = min(kMap[(i,k)][0],j)\n",
    "                    kMap[(i,k)][1] += 1\n",
    "        mCnt = 0\n",
    "        mi,mj = 0,0\n",
    "        for i,k in kMap:\n",
    "            if kMap[(i,k)][1]>=mCnt:\n",
    "                if kMap[(i,k)][1]==mCnt and (i>mi or (i==mi and j>mj)):\n",
    "                    pass\n",
    "                else:\n",
    "                    mi = i\n",
    "                    mj = kMap[(i,k)][0]\n",
    "                mCnt = kMap[(i,k)][1]\n",
    "        # print(mCnt,kMap)\n",
    "        return [mi,mj]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import gcd\n",
    "import bisect\n",
    "import copy\n",
    "import decimal\n",
    "import fractions\n",
    "import heapq\n",
    "import itertools\n",
    "import math\n",
    "import random\n",
    "import sys\n",
    "import time\n",
    "from collections import Counter, deque, defaultdict\n",
    "from functools import lru_cache, reduce\n",
    "from heapq import heappush, heappop, heapify, heappushpop\n",
    "\n",
    "\n",
    "def I(): return map(int, input().split())\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class PrimeTable:\n",
    "    def __init__(self, n:int) -> None:\n",
    "        self.n = n\n",
    "        self.primes = []\n",
    "        self.max_div = list(range(n+1))\n",
    "        self.max_div[1] = 1\n",
    "        self.phi = list(range(n+1))\n",
    "\n",
    "        for i in range(2, n + 1):\n",
    "            if self.max_div[i] == i:\n",
    "                self.primes.append(i)\n",
    "                for j in range(i, n+1, i):\n",
    "                    self.max_div[j] = i\n",
    "                    self.phi[j] = self.phi[j] // i * (i-1)\n",
    "\n",
    "    def is_prime(self, x:int):\n",
    "        if x < 2: return False\n",
    "        if x <= self.n: return self.max_div[x] == x\n",
    "        for p in self.primes:\n",
    "            if p * p > x: break\n",
    "            if x % p == 0: return False\n",
    "        return True\n",
    "\n",
    "    def prime_factorization(self, x:int):\n",
    "        if x > self.n:\n",
    "            for p in self.primes:\n",
    "                if p * p > x: break\n",
    "                if x <= self.n: break\n",
    "                if x % p == 0:\n",
    "                    cnt = 0\n",
    "                    while x % p == 0: cnt += 1; x //= p\n",
    "                    yield p, cnt\n",
    "        while (1 < x and x <= self.n):\n",
    "            p, cnt = self.max_div[x], 0\n",
    "            while x % p == 0: cnt += 1; x //= p\n",
    "            yield p, cnt\n",
    "        if x >= self.n and x > 1:\n",
    "            yield x, 1\n",
    "\n",
    "    def get_factors(self, x:int):\n",
    "        factors = [1]\n",
    "        for p, b in self.prime_factorization(x):\n",
    "            n = len(factors)\n",
    "            for j in range(1, b+1):\n",
    "                for d in factors[:n]:\n",
    "                    factors.append(d * (p ** j))\n",
    "        return factors\n",
    "\n",
    "pt = PrimeTable(10 ** 6 + 1)\n",
    "class Solution:\n",
    "    def countPaths(self, n: int, edges: List[List[int]]) -> int:\n",
    "        g = defaultdict(list)\n",
    "        for u, v in edges:\n",
    "            g[u].append(v)\n",
    "            g[v].append(u)\n",
    "        \n",
    "        def dfs(u, p, nodes):\n",
    "            nodes.append(u)\n",
    "            for v in g[u]:\n",
    "                if v == p: continue\n",
    "                if not pt.is_prime(v):\n",
    "                    dfs(v, u, nodes)\n",
    "        ans = 0\n",
    "        sz = [0] * (n + 1)\n",
    "        for x in range(1, n + 1):\n",
    "            if not pt.is_prime(x): continue\n",
    "            else:\n",
    "                curr = 0\n",
    "                for y in g[x]:\n",
    "                    if pt.is_prime(y): continue\n",
    "                    if sz[y] == 0:\n",
    "                        nodes = []\n",
    "                        dfs(y, -1, nodes)\n",
    "                        for node in nodes:\n",
    "                            sz[node] = len(nodes)\n",
    "                    ans += sz[y] * curr\n",
    "                    curr += sz[y]\n",
    "                ans += curr\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fraction(self, cont: List[int]) -> List[int]:\n",
    "        up = 1\n",
    "        down = cont[-1]\n",
    "        pre_up = up\n",
    "        pre_down = down\n",
    "        for i, c in enumerate(cont[::-1]):\n",
    "            if i == 0:\n",
    "                continue\n",
    "            now = c\n",
    "            up = pre_down\n",
    "            down = now * pre_down + pre_up\n",
    "\n",
    "            pre_down = down\n",
    "            pre_up = up\n",
    "\n",
    "        result = [down, up]\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fraction(self, cont: List[int]) -> List[int]:\n",
    "        now=[1,cont[-1]]\n",
    "        cont=cont[::-1]\n",
    "        for i in cont[1:]:\n",
    "            now[0]+=now[1]*i\n",
    "            now[0],now[1]=now[1],now[0]\n",
    "        now[0],now[1]=now[1],now[0]\n",
    "        for i in range(min(now),1,-1):\n",
    "            if now[0]%i==0 and now[1]%i==0:\n",
    "                now[0]=now[0]//i\n",
    "                now[1]=now[1]//i\n",
    "                break\n",
    "        return now"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fraction(self, cont: List[int]) -> List[int]:\n",
    "        n,m = 0, 1\n",
    "        for a in cont[::-1]:\n",
    "            n,m = m, (m * a + n)\n",
    "        return [m, n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fraction(self, cont: List[int]) -> List[int]:\n",
    "        a = 1\n",
    "        b = cont[-1]\n",
    "        for i in range(len(cont) - 2, -1 ,-1):\n",
    "            a, b = b, cont[i] * b + a\n",
    "        a, b = b, a\n",
    "        g = gcd(a, b)\n",
    "        return [a, b] if g == 1 else [a // g, b // g]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fraction(self, cont: List[int]) -> List[int]:\n",
    "        # 不用約分\n",
    "        # a3/a2*a3+1\n",
    "\n",
    "        # (a2*a3+1)/(a1 * (a2*a3+1) + a3)\n",
    "\n",
    "        # (a1 * (a2*a3+1) + a3) / a0 * (a1 * (a2*a3+1) + a3) + (a2*a3+1)\n",
    "\n",
    "\n",
    "        l = len(cont)\n",
    "        n, m = 1, cont[-1] # n/m\n",
    "        for i in range(l-2,-1,-1):\n",
    "            n, m = m, cont[i] * m + n\n",
    "\n",
    "        return [m, n]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fraction(self, cont: List[int]) -> List[int]:\n",
    "        length = len(cont)\n",
    "        if length>1:\n",
    "            q = cont[length-1]\n",
    "            p = 1\n",
    "            for i in range(length-1,0,-1):\n",
    "                tmp = q\n",
    "                q = cont[i-1]*q+p\n",
    "                p = tmp\n",
    "            t = math.gcd(p,q)\n",
    "            return [q//t,p//t]\n",
    "        else:\n",
    "            return [cont[0],1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fraction(self, cont: List[int]) -> List[int]:\n",
    "        if len(cont) == 1:\n",
    "            return [cont[0],1]\n",
    "        fm = cont[-1]\n",
    "        fz = 1\n",
    "        for i in cont[-2::-1]:\n",
    "            fz = i*fm+fz\n",
    "            fm, fz = fz, fm\n",
    "        return [fm,fz]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fraction(self, cont: List[int]) -> List[int]:\n",
    "        if len(cont) == 1:\n",
    "            return [cont[0], 1]\n",
    "        a, b = self.fraction(cont[1:])\n",
    "        return [cont[0] * a + b, a]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fraction(self, cont: List[int]) -> List[int]:\n",
    "        n = 1\n",
    "        m = cont[-1]\n",
    "        for i in range(len(cont)-2,-1,-1):\n",
    "            n,m = m ,m*cont[i]+n \n",
    "        return [m,n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fraction(self, cont: List[int]) -> List[int]:\n",
    "        def fracSum(u, d, new):\n",
    "            return new * d + u, d\n",
    "        \n",
    "        def gcf(x, y):\n",
    "            if x % y == 0:\n",
    "                return y\n",
    "            else:\n",
    "                return gcf(y, x % y)\n",
    "\n",
    "        cont.reverse()\n",
    "        u = 1\n",
    "        d = cont[0]\n",
    "        for i in cont[1:]:\n",
    "            d, u = fracSum(u, d, i)\n",
    "\n",
    "        greatestCommonFac = gcf(max(d, u), min(d, u))\n",
    "        d //= greatestCommonFac\n",
    "        u //= greatestCommonFac\n",
    "        if u < 0 and d < 0:\n",
    "            u = abs(u)\n",
    "            d = abs(d)\n",
    "        return [d, u]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fraction(self, cont: List[int]) -> List[int]:\n",
    "        n, m = 0, 1\n",
    "        for c in cont[::-1]:\n",
    "            n, m = m, (m * c + n)\n",
    "        return [m, n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fraction(self, cont: List[int]) -> List[int]:\n",
    "        n,m = 0,1\n",
    "        for a in cont[::-1]:\n",
    "            n,m = m,(a*m + n)\n",
    "        return [m,n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fraction(self, cont: List[int]) -> List[int]:\n",
    "        n, m = 0, 1\n",
    "        for num in cont[::-1]:\n",
    "            n, m = m, num * m + n\n",
    "        return [m, n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def fraction(self, cont: List[int]) -> List[int]:\n",
    "#         n=len(cont)\n",
    "#         a,b=1,cont[n-1]\n",
    "#         for i in range(n-2,-1,-1):\n",
    "#             tmp=cont[i]*b+a \n",
    "#             a,b=b,tmp \n",
    "#         f=math.gcd(a,b)\n",
    "#         return (b//f,a//f)\n",
    "\n",
    "### 网：作者：Azleal\n",
    "\n",
    "class Solution:\n",
    "    def fraction(self, cont: List[int]) -> List[int]:\n",
    "        n,m = 0, 1\n",
    "        for a in cont[::-1]:\n",
    "            n,m = m, (m * a + n)\n",
    "        return [m, n]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fraction(self, cont: List[int]) -> List[int]:\n",
    "        m,n=0,1\n",
    "        for i in cont[::-1]:\n",
    "            n,m=i*n+m,n\n",
    "        return(n,m)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fraction(self, cont: List[int]) -> List[int]:\n",
    "        if len(cont) == 1:\n",
    "            return [cont[0], 1]\n",
    "\n",
    "        def func(a, b1, b2):\n",
    "            # b1, b2 = 1, b\n",
    "            a1, a2 = a * b2, b2\n",
    "            return a1 + b1, b2\n",
    "\n",
    "        x1, x2 = func(cont[-2], 1, cont[-1])\n",
    "        for i in range(len(cont) - 3, -1, -1):\n",
    "            x1, x2 = x2, x1\n",
    "            x1, x2 = func(cont[i], x1, x2)\n",
    "        div = math.gcd(x1, x2)\n",
    "\n",
    "        return [x1 // div, x2 // div]\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fraction(self, cont: List[int]) -> List[int]:\n",
    "        # a + n/m = (a*m + n)/m\n",
    "        n, m = 0, 1\n",
    "        for a in cont[::-1]:\n",
    "            n, m = m, (m*a + n)\n",
    "        return [m, n]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fraction(self, cont: List[int]) -> List[int]:\n",
    "        up,down=1,0\n",
    "        for i in reversed(cont):\n",
    "            up,down=i*up+down,up\n",
    "            m,n=up,down\n",
    "        return [up,down]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fraction(self, cont: List[int]) -> List[int]:\n",
    "\n",
    "        def dfs(i: int) -> List[int]:\n",
    "            if i == len(cont) - 1:\n",
    "                return [cont[-1], 1]\n",
    "            x, y = dfs(i + 1)\n",
    "            # y / x + cont[i] = (y + cont[i] * x) / x \n",
    "            g = gcd(y + cont[i] * x, x)\n",
    "            return [(y + cont[i] * x) // g, x // g]\n",
    "        return dfs(0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fraction(self, cont: List[int]) -> List[int]:\n",
    "        a = 0\n",
    "        b = 1\n",
    "        for x in cont[::-1]:\n",
    "            a,b = b, (b * x + a)\n",
    "        return [b, a]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fraction(self, cont: List[int]) -> List[int]:\n",
    "        n,m = 0, 1\n",
    "        for a in cont[::-1]:\n",
    "            n, m = m, (m * a + n)\n",
    "        return [m, n]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fraction(self, cont: List[int]) -> List[int]:\n",
    "        n,m = 0, 1\n",
    "        for a in cont[::-1]:\n",
    "            n,m = m, (m * a + n)\n",
    "        return [m, n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fraction(self, cont: List[int]) -> List[int]:\n",
    "        n,m = 0,1\n",
    "        for i in range(len(cont)-1,-1,-1):\n",
    "            # pre = m\n",
    "            # m = cont[i] * m + n\n",
    "            # n = pre\n",
    "            n,m = m,(cont[i]*m + n)\n",
    "        return [m,n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fraction(self, cont: List[int]) -> List[int]:\n",
    "        # 解法一\n",
    "        n = len(cont)\n",
    "        i = 0\n",
    "        def dfs(i):\n",
    "            if i == n - 1:\n",
    "                return [cont[i], 1]\n",
    "            x = dfs(i + 1)\n",
    "            x[0], x[1] = x[1], x[0]\n",
    "            x[0] += cont[i] * x[1]\n",
    "            return x\n",
    "        res = dfs(0)\n",
    "        y = gcd(res[0], res[1])\n",
    "        res[0], res[1] = res[0] // y, res[1] // y\n",
    "        return res\n",
    "\n",
    "        # 解法二\n",
    "        # n = len(cont)\n",
    "        # if n == 1: return [cont[0], 1]\n",
    "        # res = [1, cont[n - 1]]\n",
    "        # for i in range(n - 2, 0, -1):\n",
    "        #     res[0] += cont[i] * res[1]\n",
    "        #     res[0], res[1] = res[1], res[0]\n",
    "        # res[0] += cont[0] * res[1]\n",
    "        # x = gcd(res[0], res[1])\n",
    "        # res[0], res[1] = res[0] // x, res[1] // x\n",
    "        # return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fraction(self, cont: List[int]) -> List[int]:\n",
    "        now=[1,cont[-1]]\n",
    "        cont=cont[::-1]\n",
    "        for i in cont[1:]:\n",
    "            now[0]+=now[1]*i\n",
    "            now[0],now[1]=now[1],now[0]\n",
    "        now[0],now[1]=now[1],now[0]\n",
    "        return now"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fraction(self, cont: List[int]) -> List[int]:\n",
    "        ans = [1, 0] # [分子, 分母]\n",
    "        for i in range(len(cont)-1, -1, -1):\n",
    "            t = ans[1]\n",
    "            ans[1] = ans[0] \n",
    "            ans[0] = cont[i] * ans[1] + t\n",
    "        return ans\n",
    "      "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fraction(self, cont: List[int]) -> List[int]:\n",
    "        n,m = 0, 1\n",
    "        for i in cont[::-1]:\n",
    "            n,m = m,(m*i+n)\n",
    "        return [m,n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fraction(self, cont: List[int]) -> List[int]:\n",
    "        if len(cont) == 1:\n",
    "            return [cont[0], 1]\n",
    "        l = [1, cont[-1]]\n",
    "        for i in range(len(cont) - 2, 0 ,-1):\n",
    "            tmp = l[1]\n",
    "            l[1] = cont[i] * l[1] + l[0]\n",
    "            l[0] = tmp\n",
    "        return [l[0]+cont[0]*l[1],l[1]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fraction(self, cont: List[int]) -> List[int]:\n",
    "        def gcd(a, b):\n",
    "            while b != 0:\n",
    "                a, b = b, a % b\n",
    "            return a\n",
    "        b, c = cont[-1], 1\n",
    "        p = len(cont)-2\n",
    "        while p>=0:\n",
    "            new_b = cont[p]*b + c\n",
    "            new_c = b\n",
    "            gys = gcd(new_b, new_c)\n",
    "            b = new_b//gys\n",
    "            c = new_c//gys\n",
    "            p-=1\n",
    "        return [b, c]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fraction(self, cont: List[int]) -> List[int]:\n",
    "        m,n=0,1\n",
    "        for i in cont[::-1]:\n",
    "            n,m=i*n+m,n\n",
    "        return(n,m)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fraction(self, cont: List[int]) -> List[int]:\n",
    "        fz,fm = cont[-1],1\n",
    "        for num in cont[::-1][1:]:\n",
    "            fz,fm = fm,fz\n",
    "            if num != 0:\n",
    "                fz += num * fm\n",
    "            ng = math.gcd(fz,fm)\n",
    "            fz //= ng\n",
    "            fm //= ng\n",
    "        return [fz,fm]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fraction(self, cont: List[int]) -> List[int]:\n",
    "        n,m=0,1\n",
    "        for a in cont[::-1]:\n",
    "            n,m = m, m*a+n\n",
    "        return [m,n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fraction(self, cont: List[int]) -> List[int]:\n",
    "        n,m=0,1\n",
    "        for a in cont[::-1]:\n",
    "            n,m = m, m*a+n\n",
    "        return [m,n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fraction(self, cont: List[int]) -> List[int]:\n",
    "        # def gcd(a, b):\n",
    "        #     if b == 0:\n",
    "        #         return a\n",
    "        #     if a < b:\n",
    "        #         return gcd(b, a)\n",
    "        #     return gcd(b, a%b)\n",
    "        \n",
    "        # def trim(x):\n",
    "        #     a, b = x \n",
    "        #     g = gcd(a, b)\n",
    "        #     return [a//g, b//g]\n",
    "            \n",
    "        # res = [1, 0]\n",
    "        # i = len(cont) - 1\n",
    "        # while i >= 0:\n",
    "        #     x = cont[i]\n",
    "        #     res = [res[1]+res[0]*x, res[0]]\n",
    "        #     i -= 1\n",
    "        # return trim(res) \n",
    "\n",
    "        # ----------------------\n",
    "        # res = [1, 0]\n",
    "        # i = len(cont) - 1\n",
    "        # while i >= 0:\n",
    "        #     x = cont[i]\n",
    "        #     res = [res[1]+res[0]*x, res[0]]\n",
    "        #     i -= 1\n",
    "        # return res \n",
    "\n",
    "        # ---------------\n",
    "        n,m = 0, 1\n",
    "        for a in cont[::-1]:\n",
    "            n,m = m, (m * a + n)\n",
    "        return [m, n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fraction(self, cont: List[int]) -> List[int]:\n",
    "        n,m = 0, 1\n",
    "        for a in cont[::-1]:\n",
    "            n,m = m, (m * a + n)\n",
    "        return [m, n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fraction(self, cont: List[int]) -> List[int]:\n",
    "        length = len(cont)\n",
    "        if length>1:\n",
    "            q = cont[length-1]\n",
    "            p = 1\n",
    "            for i in range(length-1,1,-1):\n",
    "                tmp = q\n",
    "                q = cont[i-1]*q+p\n",
    "                p = tmp\n",
    "            n = cont[0]*q + p\n",
    "            m = q\n",
    "            t = math.gcd(m,n)\n",
    "            return [n//t,m//t]\n",
    "        else:\n",
    "            return [cont[0],1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fraction(self, cont: List[int]) -> List[int]:\n",
    "        def gcd(a, b):\n",
    "            while b != 0:\n",
    "                a, b = b, a % b\n",
    "            return a\n",
    "        b, c = cont[-1], 1\n",
    "        cont.pop(-1)\n",
    "        while cont:\n",
    "            new_b = cont[-1]*b + c\n",
    "            new_c = b\n",
    "            gys = gcd(new_b, new_c)\n",
    "            b = new_b//gys\n",
    "            c = new_c//gys\n",
    "            cont.pop(-1)\n",
    "        return [b, c]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fraction(self, cont: List[int]) -> List[int]:\n",
    "        n = len(cont)\n",
    "        if n == 1:\n",
    "            return [cont[0], 1]\n",
    "        x, y, z = cont[n-2], cont[n - 1], 1\n",
    "        for i in range(3, n + 2):\n",
    "            t = x * y + z\n",
    "            gcd = math.gcd(y, t)\n",
    "            if i == n + 1:\n",
    "                return [t // gcd, y // gcd]\n",
    "            x, y, z = cont[n - i], t // gcd, y // gcd\n",
    "        return [-1, -1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fraction(self, cont: List[int]) -> List[int]:\n",
    "        fz=0\n",
    "        fm=1\n",
    "        for i in cont[::-1]:\n",
    "            fz,fm=fm,fm*i+fz\n",
    "        return [fm,fz]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fraction(self, cont: List[int]) -> List[int]:\n",
    "        c = 1\n",
    "        d = 0\n",
    "        for ind, i in enumerate(reversed(cont)):\n",
    "            if ind == 0:\n",
    "                c = 1\n",
    "                d = i\n",
    "            else:\n",
    "                c, d = d, c\n",
    "                d = i*c+d\n",
    "                j = math.gcd(c, d)\n",
    "                if j != 1:\n",
    "                    d = d/j\n",
    "                    c = c/j\n",
    "        return [d, c]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fraction(self, cont: List[int]) -> List[int]:\n",
    "        if len(cont) == 1:\n",
    "            return [cont[0], 1]\n",
    "        ans = [cont[-1], 1]\n",
    "        for a in reversed(cont[:-1]):\n",
    "            # 1. 分子分母互换\n",
    "            ans[0], ans[1] = ans[1], ans[0]\n",
    "            # 2. 分母不变，重新计算分子\n",
    "            ans[0] += a * ans[1]\n",
    "        # 找最大公约数\n",
    "        gcd_val = gcd(ans[0], ans[1])\n",
    "        ans[0], ans[1] = ans[0] // gcd_val, ans[1] // gcd_val\n",
    "        return ans\n",
    "    \n",
    "    def gcd(a: int, b: int) -> int:\n",
    "        if b == 0:\n",
    "            return a\n",
    "        return gcd(b, b % a)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fraction(self, cont: List[int]) -> List[int]:\n",
    "        prev_n = 0\n",
    "        prev_d = 1\n",
    "\n",
    "        def gcd(a, b):\n",
    "            return a if b == 0 else gcd(b, a % b)\n",
    "\n",
    "        def fraction_add(a_n,a_d,b_n,b_d):\n",
    "            n = a_n * b_d + a_d * b_n \n",
    "            d = a_d * b_d \n",
    "\n",
    "            gd = gcd(n, d)\n",
    "\n",
    "            return n // gd, d // gd\n",
    "\n",
    "\n",
    "        for i in range(len(cont) - 1, -1, -1):\n",
    "            # prev += cont[i]\n",
    "            prev_n, prev_d = fraction_add(prev_n, prev_d, cont[i], 1)\n",
    "            if i == 0:\n",
    "                # return prev\n",
    "                return [prev_n, prev_d]\n",
    "            # prev = 1 / prev\n",
    "            prev_n, prev_d = prev_d, prev_n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# https://leetcode.cn/problems/deep-dark-fraction/description/\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    # 摘录自：https://leetcode.cn/problems/deep-dark-fraction/description/comments/2070320\n",
    "    # 按照数学方法反推， f[n-1] = up/down, f[n-2] = an-2 + down/up = (an-2 * up + down) / up, ... ,\n",
    "    # 也就相当于在遍历中， up => ai * up + down, down => up， 通过不断的同时交换生成新的分子分母获得最后的结果\n",
    "    def fraction(self, cont: List[int]) -> List[int]:\n",
    "        fenzi, fenmu, n = 1, 0, cont.__len__()\n",
    "        for i in range(n-1, -1, -1):\n",
    "            fenzi, fenmu = fenmu + cont[i] * fenzi, fenzi\n",
    "        return [fenzi, fenmu]\n",
    "\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    s = Solution()\n",
    "    for testcase in [\n",
    "        [3, 2, 0, 2],\n",
    "        [0, 0, 3],\n",
    "    ]:\n",
    "        ret = s.fraction(testcase)\n",
    "        print(\"testcase={}, ret={}\".format(testcase, ret))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fraction(self, cont: List[int]) -> List[int]:\n",
    "        n = len(cont)\n",
    "        numer, denom = cont[n - 1], 1\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            numer, denom = denom, numer\n",
    "            numer += cont[i] * denom\n",
    "        gcd = math.gcd(numer, denom)\n",
    "        return [numer // gcd, denom // gcd]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fraction(self, cont: List[int]) -> List[int]:\n",
    "        i=len(cont)-1\n",
    "        b=[1,cont[-1]]\n",
    "        while i>0:\n",
    "            a=[cont[i-1],1]\n",
    "            b=[a[1]*b[1],a[0]*b[1]+a[1]*b[0]]\n",
    "            i-=1\n",
    "        num=reduce(gcd,b)\n",
    "        return [b[1]//num,b[0]//num]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fraction(self, cont: List[int]) -> List[int]:\n",
    "        # def gcd(a, b):\n",
    "        #     if b == 0:\n",
    "        #         return a\n",
    "        #     if a < b:\n",
    "        #         return gcd(b, a)\n",
    "        #     return gcd(b, a%b)\n",
    "        \n",
    "        # def trim(x):\n",
    "        #     a, b = x \n",
    "        #     g = gcd(a, b)\n",
    "        #     return [a//g, b//g]\n",
    "            \n",
    "        # res = [1, 0]\n",
    "        # i = len(cont) - 1\n",
    "        # while i >= 0:\n",
    "        #     x = cont[i]\n",
    "        #     res = [res[1]+res[0]*x, res[0]]\n",
    "        #     i -= 1\n",
    "        # return trim(res) \n",
    "\n",
    "        # ----------------------\n",
    "        res = [1, 0]\n",
    "        i = len(cont) - 1\n",
    "        while i >= 0:\n",
    "            x = cont[i]\n",
    "            res = [res[1]+res[0]*x, res[0]]\n",
    "            i -= 1\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fraction(self, cont: List[int]) -> List[int]:\n",
    "        n=len(cont)\n",
    "        def f(i):\n",
    "            if i==n-1:\n",
    "                return (1,cont[i])\n",
    "            a,b=f(i+1)\n",
    "            return (b,cont[i]*b+a)\n",
    "        a,b=f(0)\n",
    "        def gcd(a,b):\n",
    "            if a%b==0:\n",
    "                return b\n",
    "            return gcd(b,a%b)\n",
    "        g=gcd(a,b)\n",
    "        return [b//g,a//g]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fraction(self, cont: List[int]) -> List[int]:\n",
    "        n=0\n",
    "        m=1\n",
    "        for a in cont[::-1]:\n",
    "            m,n=a*m+n,m\n",
    "        return [m,n]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fraction(self, cont: List[int]) -> List[int]:\n",
    "        n,m = 0, 1\n",
    "        for a in cont[::-1]:\n",
    "            n,m = m, (m * a + n)\n",
    "        return [m, n]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fraction(self, cont: List[int]) -> List[int]:\n",
    "        n, m = 0, 1\n",
    "        for i in cont[::-1]:\n",
    "            n, m = m, (m * i + n)\n",
    "        return [m, n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fraction(self, cont: List[int]) -> List[int]:\n",
    "        n=0\n",
    "        m=1\n",
    "        for i in cont[::-1]:\n",
    "            x=m\n",
    "            m=i*x+n\n",
    "            n=x\n",
    "        return[m,n]\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fraction(self, cont: List[int]) -> List[int]:\n",
    "        n,m = 0, 1\n",
    "        for a in cont[::-1]:\n",
    "            n,m = m, (m * a + n)\n",
    "        return [m, n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fraction(self, cont: List[int]) -> List[int]:\n",
    "        n, m = 0, 1\n",
    "        for i in cont[::-1]:\n",
    "            n, m = m, (m*i+n)\n",
    "        return [m,n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fraction(self, cont: List[int]) -> List[int]:\n",
    "        if not cont:\n",
    "            return [1, 1]\n",
    "        length = len(cont)\n",
    "        if length == 1:\n",
    "            return [cont[0], 1]\n",
    "        if length == 2:\n",
    "            return self.helper(cont[0], cont[1], 1)\n",
    "        [n, m] = self.helper(cont[length -2], cont[length - 1], 1)\n",
    "        for i in range(length - 3, -1, -1):\n",
    "            [n, m] = self.helper(cont[i], n, m)\n",
    "        return [n, m]     \n",
    "\n",
    "    def helper(self, num1: int, num2numerator: int, num2denominator: int) -> [int, int]:\n",
    "        numerator = num1 * num2numerator + num2denominator\n",
    "        denominator = num2numerator\n",
    "        return [numerator, denominator]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fraction(self, cont: List[int]) -> List[int]:\n",
    "\n",
    "        numerator = cont[-1]\n",
    "        denominator = 1\n",
    "\n",
    "        for c in cont[:-1][::-1]:\n",
    "            numerator, denominator = denominator, numerator\n",
    "            numerator += c*denominator\n",
    "        \n",
    "        # print(f'{numerator} {denominator}')\n",
    "\n",
    "        if v := gcd(numerator, denominator) != 1:\n",
    "            numerator = numerator // v\n",
    "            denominator = denominator // v\n",
    "        \n",
    "        # print(f'{numerator} {denominator}')\n",
    "\n",
    "        return [numerator, denominator]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fraction(self, cont: List[int]) -> List[int]:\n",
    "        fz,fm = cont[-1],1\n",
    "        for num in cont[::-1][1:]:\n",
    "            fz,fm = fm,fz\n",
    "            if num != 0:\n",
    "                nfz = num * fm\n",
    "                fz += nfz\n",
    "            ng = math.gcd(fz,fm)\n",
    "            fz //= ng\n",
    "            fm //= ng\n",
    "        return [fz,fm]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fraction(self, cont: List[int]) -> List[int]:\n",
    "        if len(cont) == 1:\n",
    "            return [cont[0],1]\n",
    "        contR = cont[::-1]\n",
    "        result = [0,1]\n",
    "        for index,item in enumerate(contR):\n",
    "            if index == 0:\n",
    "                result = [1,item]\n",
    "            else:\n",
    "                result = [item * result[1] + result[0],result[1]]\n",
    "                result = result[::-1]\n",
    "        else:\n",
    "            result = result[::-1]\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fraction(self, cont: List[int]) -> List[int]:\n",
    "        n = len(cont)\n",
    "        if n == 1:\n",
    "            return [cont[0], 1]\n",
    "        x, y, z = cont[n-2], cont[n - 1], 1\n",
    "        for i in range(3, n + 2):\n",
    "            t = x * y + z\n",
    "            # gcd = math.gcd(y, t)\n",
    "            gcd = 1\n",
    "            if i == n + 1:\n",
    "                return [t // gcd, y // gcd]\n",
    "            x, y, z = cont[n - i], t // gcd, y // gcd\n",
    "        return [-1, -1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fraction(self, cont: List[int]) -> List[int]:\n",
    "        n,m = 0, 1\n",
    "        for a in cont[::-1]:\n",
    "            n,m = m, (m * a + n)\n",
    "        return [m, n]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fraction(self, cont: List[int]) -> List[int]:\n",
    "        fenzi,fenmu=1,0\n",
    "        for a in cont[::-1]:\n",
    "            fenzi,fenmu=fenzi*a+fenmu,fenzi \n",
    "        return [fenzi,fenmu]\n",
    "\n",
    "\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fraction(self, cont: List[int]) -> List[int]:\n",
    "        n,m = 0,1\n",
    "        for i in range(len(cont)-1,-1,-1):\n",
    "            # pre = m\n",
    "            # m = cont[i] * m + n\n",
    "            # n = pre\n",
    "            n,m = m,(cont[i]*m + n)\n",
    "        return [m,n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fraction(self, cont: List[int]) -> List[int]:\n",
    "        a = cont[-1]\n",
    "        b = 1\n",
    "        for i in range(len(cont) - 2, -1, -1):\n",
    "            a,b = b,a\n",
    "            a = cont[i] * b + a\n",
    "            print(a)\n",
    "            print(b)\n",
    "        gcd = math.gcd(a, b)\n",
    "        return [a// gcd, b//gcd]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import fractions\n",
    "\n",
    "class Solution:\n",
    "    def fraction(self, cont: List[int]) -> List[int]:\n",
    "        cont = list(reversed(cont))\n",
    "        ret = None\n",
    "        for i, n in enumerate(cont):\n",
    "            if i == 0:\n",
    "                ret = fractions.Fraction(n, 1)\n",
    "            else:\n",
    "                ret = n + 1 / ret\n",
    "        return [ret.numerator, ret.denominator]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fraction(self, cont: List[int]) -> List[int]:\n",
    "        n,m=0,1\n",
    "        for a in cont[::-1]:\n",
    "            n,m=m,(m*a+n)\n",
    "        return [m,n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fraction(self, cont: List[int]) -> List[int]:\n",
    "        # 解法一\n",
    "        # n = len(cont)\n",
    "        # i = 0\n",
    "        # def dfs(i):\n",
    "        #     if i == n - 1:\n",
    "        #         return [cont[i], 1]\n",
    "        #     x = dfs(i + 1)[::-1]\n",
    "        #     x[0] += cont[i] * x[1]\n",
    "        #     return x\n",
    "        # res = dfs(0)\n",
    "        # y = gcd(res[0], res[1])\n",
    "        # res[0], res[1] = res[0] // y, res[1] // y\n",
    "        # return res\n",
    "\n",
    "        # 解法二\n",
    "        n = len(cont)\n",
    "        if n == 1: return [cont[0], 1]\n",
    "        res = [1, cont[n - 1]]\n",
    "        for i in range(n - 2, 0, -1):\n",
    "            res[0] += cont[i] * res[1]\n",
    "            res[0], res[1] = res[1], res[0]\n",
    "        res[0] += cont[0] * res[1]\n",
    "        x = gcd(res[0], res[1])\n",
    "        res[0], res[1] = res[0] // x, res[1] // x\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fraction(self, cont: List[int]) -> List[int]:\n",
    "        n,m = 0,1\n",
    "        for i in range(len(cont)-1,-1,-1):\n",
    "            pre = m\n",
    "            m = cont[i] * m + n\n",
    "            n = pre\n",
    "        return [m,n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fraction(self, cont: List[int]) -> List[int]:\n",
    "        if len(cont) == 1:\n",
    "            return [cont[0],1]\n",
    "        if len(cont) == 2:\n",
    "            return [cont[0]*cont[1]+1 , cont[1]]\n",
    "        else:\n",
    "            a = self.fraction(cont[1:])\n",
    "            return [cont[0]*a[0] + a[1], a[0]]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fraction(self, cont: List[int]) -> List[int]:\n",
    "        length = len(cont)\n",
    "        if length==1:\n",
    "            return [cont[0],1]\n",
    "        q = cont[length-1]\n",
    "        p = 1\n",
    "        for i in range(length-1,1,-1):\n",
    "            tmp = q\n",
    "            q = cont[i-1]*q+p\n",
    "            p = tmp\n",
    "        n = cont[0]*q + p\n",
    "        m = q\n",
    "        t = math.gcd(m,n)\n",
    "        print(t)\n",
    "        return [n//t,m//t]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fraction(self, cont: List[int]) -> List[int]:\n",
    "        def gcd(a, b):\n",
    "            if b == 0:\n",
    "                return a\n",
    "            if a < b:\n",
    "                return gcd(b, a)\n",
    "            return gcd(b, a%b)\n",
    "        \n",
    "        def trim(x):\n",
    "            a, b = x \n",
    "            g = gcd(a, b)\n",
    "            return [a//g, b//g]\n",
    "            \n",
    "        res = [1, 0]\n",
    "        i = len(cont) - 1\n",
    "        while i >= 0:\n",
    "            x = cont[i]\n",
    "            res = [res[1]+res[0]*x, res[0]]\n",
    "            i -= 1\n",
    "        return trim(res) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fraction(self, cont: List[int]) -> List[int]:\n",
    "        length = len(cont)\n",
    "        if length>1:\n",
    "            q = cont[length-1]\n",
    "            p = 1\n",
    "            for i in range(length-1,0,-1):\n",
    "                tmp = q\n",
    "                q = cont[i-1]*q+p\n",
    "                p = tmp\n",
    "            # n = cont[0]*q + p\n",
    "            # m = q\n",
    "            # t = math.gcd(m,n)\n",
    "            # return [n//t,m//t]\n",
    "            t = math.gcd(p,q)\n",
    "            return [q//t,p//t]\n",
    "        else:\n",
    "            return [cont[0],1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fraction(self, cont: List[int]) -> List[int]:\n",
    "        # 解法一\n",
    "        # n = len(cont)\n",
    "        # i = 0\n",
    "        # def dfs(i):\n",
    "        #     if i == n - 1:\n",
    "        #         return [cont[i], 1]\n",
    "        #     x = dfs(i + 1)[::-1]\n",
    "        #     x[0] += cont[i] * x[1]\n",
    "        #     return x\n",
    "        # res = dfs(0)\n",
    "        # y = gcd(res[0], res[1])\n",
    "        # res[0], res[1] = res[0] // y, res[1] // y\n",
    "        # return res\n",
    "\n",
    "        # 解法二\n",
    "        n = len(cont)\n",
    "        if n == 1: return [cont[0], 1]\n",
    "        res = [1, cont[n - 1]]\n",
    "        for i in range(n - 2, 0, -1):\n",
    "            res[0] += cont[i] * res[1]\n",
    "            res = res[::-1]\n",
    "        res[0] += cont[0] * res[1]\n",
    "        x = gcd(res[0], res[1])\n",
    "        res[0], res[1] = res[0] // x, res[1] // x\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fraction(self, cont: List[int]) -> List[int]:\n",
    "        n,m = 0, 1\n",
    "        for a in cont[::-1]:\n",
    "            n,m = m, (m * a + n)\n",
    "        return [m, n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fraction(self, cont: List[int]) -> List[int]:\n",
    "        n,m = 0, 1\n",
    "        for a in cont[::-1]:\n",
    "            n,m = m, (m * a + n)\n",
    "        return [m, n]\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
